Trémaux tree

In graph theory a Trémaux tree of a graph G is a spanning tree of G, rooted at one of its vertices, with the property that every edge in G connects a pair of vertices that are related as ancestor and descendant in the tree. In a depth-first search of a graph, the tree of edges by which each vertex was first reached (also called a depth-first search tree) is necessarily a Trémaux tree. Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French mathematician who used a form of depth-first search as a strategy for solving mazes.[1][2]

If a graph has a Hamiltonian path, then that path (rooted at one of its endpoints) is a Trémaux tree. For an example of a spanning tree that is not a Tremaux tree, let G be the triangle graph with root u. The tree consisting of the edges uv and uw is not a Tremaux tree, because the edge vw is not in the tree, but v and w are equally far from the root.

Trémaux trees play a key role in Fraysseix–Rosenstiehl's planarity criterion for testing whether a given graph is planar.[3]

References

  1. ^ Even, Shimon (2011), Graph Algorithms (2nd ed.), Cambridge University Press, pp. 46–48, ISBN 9780521736534, http://books.google.com/books?id=m3QTSMYm5rkC&pg=PA46 .
  2. ^ Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms (3rd ed.), Pearson Education, pp. 149–157, ISBN 9780201361186, http://books.google.com/books?id=0rLN_tcvD-IC&pg=PT149 .
  3. ^ de Fraysseix, Hubert; Rosenstiehl, Pierre (1982), "A depth-first-search characterization of planarity", Graph theory (Cambridge, 1981), Ann. Discrete Math., 13, Amsterdam: North-Holland, pp. 75–80, MR671906 ; de Fraysseix, Hubert; de Mendez, Patrice Ossona; Rosenstiehl, Pierre (2006), "Trémaux trees and planarity", International Journal of Foundations of Computer Science 17 (5): 1017–1029, doi:10.1142/S0129054106004248, MR2270949 .